package com.study.lu.动态规划;

public class 最佳观光组合 {
    /**
     * 给你一个正整数数组 values，其中 values[i]表示第 i 个观光景点的评分，并且两个景点i 和j之间的 距离 为j - i。
     * <p>
     * 一对景点（i < j）组成的观光组合的得分为 values[i] + values[j] + i - j ，也就是景点的评分之和 减去 它们两者之间的距离。
     * <p>
     * 返回一对观光景点能取得的最高分。
     * <p>
     * <p>
     * <p>
     * 示例 1：
     * <p>
     * 输入：values = [8,1,5,2,6]
     * 输出：11
     * 解释：i = 0, j = 2, values[i] + values[j] + i - j = 8 + 5 + 0 - 2 = 11
     * 示例 2：
     * <p>
     * 输入：values = [1,2]
     * 输出：2
     * <p>
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/best-sightseeing-pair
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     *
     * @param args
     */
    public static void main(String[] args) {
        //int[] values = new int[]{1, 3, 5};
        //  int[] values = new int[]{1, 2};
        int[] values = new int[]{8, 1, 5, 2, 6};
        System.out.println(maxScoreSightseeingPair(values));
        System.out.println(maxScoreSightseeingPair2(values));
    }

    /**
     * 由题中给的公式可得  values[i] + values[j] + i - j
     * 很容易想到双指针 i,j i从头开始，j从尾部开始
     * 把公式进行变换下 (values[i]+i) + (values[j]-j)
     * [8,1,5,2,6]
     * i=0:values[i]+i=8+0=8;j=1:values[j]-j=1-1=0;两部分相加总和为8+0=8;j++
     * i=0:values[i]+i=8+0=8;j=2:values[2]-2=5-2=3;两部分相加总和为8+3=11;j++.
     * i=0:values[i]+i=8+0=8;j=3:values[3]-3=2-3=-1;两部分相加总和为8-1=7;i++.
     * ...
     * <p>
     * 可得 i 什么时候变动就是看 i? values[j]+j>=values[i]+i  即 values[j]>=values[i]+i -j;
     *
     * @param values
     * @return
     */
    private static int maxScoreSightseeingPair2(int[] values) {
        int i = 0, j = 1, max = values[0];

        while (j < values.length) {
            int temp = values[j] - j + values[i] + i;
            max = Math.max(temp, max);
            // i 越大越好
            if (values[j] + j >= values[i] + i) {
                i = j;
            }
            j++;


        }

        return max;

    }

    /**
     * i,j  i<j
     * values[i] + values[j] + i - j
     * ( values[i] + i ) + ( values[j] - j )
     * <p>
     * 要保证 values[i] + i 都是最大值的时候  ( values[j] - j )也是最大值，并且i<j
     * <p>
     *
     * @param values
     * @return
     */
    public static int maxScoreSightseeingPair(int[] values) {
        int dp_i_1 = values[0];
        int maxScore = values[0];

        for (int i = 1; i < values.length; i++) {
            // 1. 先取 公式中 ( values[i] + i ) + ( values[j] - j ) 的  ( values[i] + i )最大值。
            int dp_i = Math.max(dp_i_1, values[i - 1] + i - 1);
            // 2. 再取 ( values[j] - j ) 的值 ，这个值加上dp_i 就是 i到j的最大值。然后与maxScore进行比较
            maxScore = Math.max(maxScore, dp_i + values[i] - i);
            dp_i_1 = dp_i;
        }

        return maxScore;

    }
}
